#ifndef _LOCK_FREE_H_
#define _LOCK_FREE_H_

#include <sched.h>
#include <atomic>
#include <iostream>

namespace lockfree
{
    template<typename T>
    class node
    {
    public:
        T value;
        std::atomic<node<T>*> next;
        
        node():next(NULL)
        {
            
        }
        ~node() 
        {
        }
    };

    template<typename T> 
    class queue
    {
        typedef node<T> node_type;
    public:
    
        queue()
        {
            m_tail = m_head = new node_type();
            m_allow = 0;
            m_size = 0;
        }
    
        ~queue()
        {
        }

        void push(T& data)
        {
            node_type* node = new node_type();
            
            node->value = std::move(data);
            node_type* tail, *next, *temp;

            while (true)
            {
                tail = m_tail.load();
                next = tail->next;
                
                if (tail != m_tail) continue;
    
                if (NULL != next)
                {
                    temp = next;
                    m_tail.compare_exchange_strong(tail, temp);
                    continue;
                }
                temp = node;

                if (tail->next.compare_exchange_strong(next, temp)) break;
            }

            m_size = m_size + 1;
            temp = node;
            m_tail.compare_exchange_strong(tail, temp);
        }
    
        bool pop(T & data)
        {
            node_type* head, *tail, *next, *temp;
            int cur = 0, dst = 1;

            while (true)
            {
                head = m_head.load();
                tail = m_tail.load();
                next = head->next.load();
                
                if (head != m_head.load()) continue;
    
                if (head == tail)
                {
                    if (next == NULL)
                    {
                        return false;
                    }
                    temp = next;

                    m_tail.compare_exchange_strong(tail, temp);
                }
                else
                {
                    while(!m_allow.compare_exchange_weak(
                        cur, dst, std::memory_order_release, std::memory_order_acquire)
                        )
                    {
                        cur = 0;
                        sched_yield();
                    }
                    
                    if(m_head != head)
                    {
                        m_allow.store(0, std::memory_order_release);
                        continue;
                    }
                    
                    temp = next;
                    if (m_head.compare_exchange_strong(head, temp))
                    {
                        m_size = m_size - 1;
                        data = std::move(next->value);
                        m_allow.store(0, std::memory_order_release);
                        break;
                    }
                    else
                    {
                        m_allow.store(0, std::memory_order_release);
                        continue;
                    }
                }
            }
            delete head;
            return true;
        }
        
        bool empty() 
        {
            return m_head == m_tail;
        }

        int size()
        {
            return m_size;
        }

        void clear()
        {
            T temp;
            while (this->pop(temp));
        }

    private:

        int m_size = 0;
        std::atomic<node_type*>  m_head, m_tail;
        std::atomic<int>    m_allow;
    };
}

#endif /*_LOCK_FREE_H_*/